<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,100分)- 悄悄话（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>给定一个二叉树&#xff0c;每个节点上站一个人&#xff0c;节点数字表示父节点到该节点传递悄悄话需要花费的时间。</p> 
<p>初始时&#xff0c;根节点所在位置的人有一个悄悄话想要传递给其他人&#xff0c;求二叉树所有节点上的人都接收到悄悄话花费的时间。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>给定二叉树</p> 
<blockquote> 
 <p>0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2</p> 
</blockquote> 
<p>注&#xff1a;-1表示空节点</p> 
<p><img alt="" height="353" src="https://img-blog.csdnimg.cn/fa48ff09af474377babcb793c5352a28.png" width="358" /></p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>返回所有节点都接收到悄悄话花费的时间</p> 
<blockquote> 
 <p>38</p> 
</blockquote> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">38</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>题目给的输入信息对照图示来看&#xff0c;应该就是二叉树的层序遍历序列&#xff0c;如下图所示&#xff1a;</p> 
<p><img alt="" height="304" src="https://img-blog.csdnimg.cn/direct/534ffed960dc4adea53d7ddc9198c0e3.png" width="387" /></p> 
<p>层序遍历序列中&#xff0c;父子节点存在如下关系&#xff1a;</p> 
<blockquote> 
 <p>如果父节点在序列中的索引是k&#xff0c;则其两个子节点在序列中的索引分别为 2k&#43;1, 2k&#43;2</p> 
</blockquote> 
<p>因此&#xff0c;我们就无需建树操作了。</p> 
<p></p> 
<p>而悄悄话的传递&#xff0c;其实父节点将自身得到消息的时延累加到其各个子节点上&#xff0c;最终叶子节点中最大的时延值就是&#xff1a;二叉树所有节点上的人都接收到悄悄话花费的时间</p> 
<p><img alt="" height="335" src="https://img-blog.csdnimg.cn/direct/8cc7ebc6f77a47f3b1a785979b40289a.png" width="425" /></p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81" style="background-color:transparent;">JS算法源码</h4> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

void (async function () {
  const times &#61; (await readline()).split(&#34; &#34;).map(Number);

  // 记录题解
  let ans &#61; 0;

  // 根节点的索引是0
  const queue &#61; [0];
  while (queue.length &gt; 0) {
    const fa &#61; queue.shift(); // 父节点索引

    const ch1 &#61; 2 * fa &#43; 1; // 左子节点索引
    const ch2 &#61; 2 * fa &#43; 2; // 右子节点索引

    // fa是否存在左子节点
    const ch1_exist &#61; ch1 &lt; times.length &amp;&amp; times[ch1] !&#61; -1;
    // fa是否存在右子节点
    const ch2_exist &#61; ch2 &lt; times.length &amp;&amp; times[ch2] !&#61; -1;

    // fa如果存在左子节点
    if (ch1_exist) {
      times[ch1] &#43;&#61; times[fa];
      queue.push(ch1);
    }

    // fa如果存在右子节点
    if (ch2_exist) {
      times[ch2] &#43;&#61; times[fa];
      queue.push(ch2);
    }

    // fa是叶子节点
    if (!ch1_exist &amp;&amp; !ch2_exist) {
      // 保留叶子节点中最大时延
      ans &#61; Math.max(ans, times[fa]);
    }
  }

  console.log(ans);
})();
</code></pre> 
<p> </p> 
<h4 style="background-color:transparent;">Java算法源码</h4> 
<pre><code class="language-java">import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int[] times &#61; Arrays.stream(sc.nextLine().split(&#34; &#34;)).mapToInt(Integer::parseInt).toArray();

    // 记录题解
    int ans &#61; 0;

    // 根节点的索引是0
    LinkedList&lt;Integer&gt; queue &#61; new LinkedList&lt;&gt;();
    queue.addLast(0);

    while (queue.size() &gt; 0) {
      int fa &#61; queue.removeFirst(); // 父节点索引

      int ch1 &#61; 2 * fa &#43; 1; // 左子节点索引
      int ch2 &#61; 2 * fa &#43; 2; // 右子节点索引

      // fa是否存在左子节点
      boolean ch1_exist &#61; ch1 &lt; times.length &amp;&amp; times[ch1] !&#61; -1;
      // fa是否存在右子节点
      boolean ch2_exist &#61; ch2 &lt; times.length &amp;&amp; times[ch2] !&#61; -1;

      // fa如果存在左子节点
      if (ch1_exist) {
        times[ch1] &#43;&#61; times[fa];
        queue.addLast(ch1);
      }

      // fa如果存在右子节点
      if (ch2_exist) {
        times[ch2] &#43;&#61; times[fa];
        queue.addLast(ch2);
      }

      // fa是叶子节点
      if (!ch1_exist &amp;&amp; !ch2_exist) {
        // 保留叶子节点中最大时延
        ans &#61; Math.max(ans, times[fa]);
      }
    }

    System.out.println(ans);
  }
}
</code></pre> 
<p> </p> 
<h4 style="background-color:transparent;">Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
times &#61; list(map(int, input().split()))


# 算法入口
def getResult():
    # 记录题解
    ans &#61; 0

    # 根节点的索引是0
    queue &#61; [0]
    while len(queue) &gt; 0:
        fa &#61; queue.pop(0)  # 父节点索引

        ch1 &#61; 2 * fa &#43; 1  # 左子节点索引
        ch2 &#61; 2 * fa &#43; 2  # 右子节点索引

        # fa是否存在左子节点
        ch1_exist &#61; ch1 &lt; len(times) and times[ch1] !&#61; -1
        # fa是否存在右子节点
        ch2_exist &#61; ch2 &lt; len(times) and times[ch2] !&#61; -1

        # fa如果存在左子节点
        if ch1_exist:
            times[ch1] &#43;&#61; times[fa]
            queue.append(ch1)

        # fa如果存在右子节点
        if ch2_exist:
            times[ch2] &#43;&#61; times[fa]
            queue.append(ch2)

        # fa是叶子节点
        if not ch1_exist and not ch2_exist:
            # 保留叶子节点中最大时延
            ans &#61; max(ans, times[fa])

    return ans


# 算法调用
print(getResult())
</code></pre> 
<p></p> 
<h4 style="background-color:transparent;">C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

#define MAX(a,b) ((a) &gt; (b) ? (a) : (b))

#define MAX_SIZE 10000

typedef struct ListNode {
    int ele;
    struct ListNode *next;
} ListNode;

typedef struct LinkedList {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

LinkedList *new_LinkedList() {
    LinkedList *link &#61; (LinkedList *) malloc(sizeof(LinkedList));
    link-&gt;size &#61; 0;
    link-&gt;head &#61; NULL;
    link-&gt;tail &#61; NULL;
    return link;
}

void addLast_LinkedList(LinkedList *link, int ele) {
    ListNode *listNode &#61; (ListNode *) malloc(sizeof(ListNode));
    listNode-&gt;ele &#61; ele;
    listNode-&gt;next &#61; NULL;

    if(link-&gt;size &#61;&#61; 0) {
        link-&gt;head &#61; listNode;
        link-&gt;tail &#61; listNode;
    } else {
        link-&gt;tail-&gt;next &#61; listNode;
        link-&gt;tail &#61; listNode;
    }

    link-&gt;size&#43;&#43;;
}

int removeFirst_LinkedList(LinkedList* link) {
    if(link-&gt;size &#61;&#61; 0) exit(-1);

    ListNode* removed &#61; link-&gt;head;

    if(link-&gt;size &#61;&#61; 1) {
        link-&gt;head &#61; NULL;
        link-&gt;tail &#61; NULL;
    } else {
        link-&gt;head &#61; link-&gt;head-&gt;next;
    }

    link-&gt;size--;

    int res &#61; removed-&gt;ele;

    free(removed);

    return res;
}

int main() {
    int times[MAX_SIZE];
    int times_size &#61; 0;

    while (scanf(&#34;%d&#34;, &amp;times[times_size&#43;&#43;])) {
        if(getchar() !&#61; &#39; &#39;) break;
    }

    // 记录题解
    int ans &#61; 0;

    // 根节点的索引是0
    LinkedList* queue &#61; new_LinkedList();
    addLast_LinkedList(queue, 0);

    while (queue-&gt;size &gt; 0) {
        int fa &#61; removeFirst_LinkedList(queue); // 父节点索引

        int ch1 &#61; 2 * fa &#43; 1; // 左子节点索引
        int ch2 &#61; 2 * fa &#43; 2; // 右子节点索引

        // fa是否存在左子节点
        int ch1_exist &#61; ch1 &lt; times_size &amp;&amp; times[ch1] !&#61; -1;
        // fa是否存在右子节点
        int ch2_exist &#61; ch2 &lt; times_size &amp;&amp; times[ch2] !&#61; -1;

        // fa如果存在左子节点
        if(ch1_exist) {
            times[ch1] &#43;&#61; times[fa];
            addLast_LinkedList(queue, ch1);
        }

        // fa如果存在右子节点
        if(ch2_exist) {
            times[ch2] &#43;&#61; times[fa];
            addLast_LinkedList(queue, ch2);
        }

        // fa是叶子节点
        if(!ch1_exist &amp;&amp; !ch2_exist) {
            // 保留叶子节点中最大时延
            ans &#61; MAX(ans, times[fa]);
        }
    }

    printf(&#34;%d\n&#34;, ans);

    return 0;
}</code></pre> 
<p></p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>